#include "main/utils.h"
using namespace std;

static bool cmp(pair<int, int>& m, pair<int, int>& n) {
  return m.second > n.second;
}

vector<int> topKFrequent(const vector<int> &vec, const int& k) {
  unordered_map<int, int> help_map;
  for (int i = 0; i < vec.size(); ++i) {
    help_map[vec[i]]++;
  }

  priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> p_queue(cmp);
  for (auto &ele : help_map) {
    if (p_queue.size() < k) {
      p_queue.emplace(ele.first, ele.second);
    } else {
      if (p_queue.top().second < ele.second) {
        p_queue.pop();
        p_queue.emplace(ele.first, ele.second);
      }
    }
  }

  std::vector<int> ret;
  while (!p_queue.empty()) {
    ret.push_back(p_queue.top().first);
    p_queue.pop();
  }
  return ret;
}

int main() {
  vector<int> vec = {1, 2, 2, 1, 3, 1, 3, 3, 3, 3};
  auto ret = topKFrequent(vec, 2);
  printVec("o60", ret);

  return 0;
}
